package 左哥算法.ch02二分;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * 我们采用左闭有闭时，l=mid+1,r=mid-1
 * 你判断个几把，多加个if会死？
 *
 */
public class 找到等于 {
    @Test
    public void test() {
        int[] arr = {1, 2, 2, 2, 5};
        int first = findFirst(arr, 6);
        System.out.println(first);
    }

    /**
     * 二分查找,找到一个等于n的数（并不一定是第一个）
     */
    public int find(int[] arr, int n) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int mid = l + r >> 1;
            if (n < arr[mid]) {
                r = mid - 1;
            } else if (n > arr[mid]) {
                l = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 二分查找,找到第一个等于n的数
     */
    public int findFirst(int[] arr, int n) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int mid = l + r >> 1;
            if (n <= arr[mid]) {    //因为 r是mid-1，所以当l==r时，这里一定为false（r不是0的时候）
                r = mid - 1;     //这里是最后一个符合要求的数
            } else {
                l = mid + 1;
            }
        }
        if (l < arr.length && arr[l] == n) {
            return l;
        }
        return -1;
    }

    /**
     * 查找最后一个等于
     */
    public int findLast(int[] arr, int n) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int mid = l + r >> 1;
            if (n >= arr[mid]) {
                l = mid + 1;    //这里是给谁赋值，谁就是越过的那个，这里l越过r
            } else {
                r = mid - 1;    //这里是最后一个符合要求的数
            }
        }
        if (r >= 0 && arr[r] == n) {
            return r;
        }
        return -1;
    }

    //测试等于
    @Test
    public void compare() {
        int count = 10000;
        Random r = new Random();
        while (count-- > 0) {
            int n = r.nextInt(Short.MAX_VALUE) + 1;
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = r.nextInt(Short.MAX_VALUE);
            }
            Arrays.sort(arr);
            int x = r.nextInt(Short.MAX_VALUE);
            int ans = ans(arr, x);
            int find = find(arr, x);
            if (ans != find && arr[ans] != arr[find]) {
                System.out.println("出错了");
                System.out.println(Arrays.toString(arr));
                System.out.println(x);
                System.out.println(ans);
                System.out.println(find);
                break;
            }
        }
    }

    //测试第一个等于
    @Test
    public void compareFirst() {
        int count = 10000;
        Random r = new Random();
        while (count-- > 0) {
            int n = r.nextInt(Short.MAX_VALUE) + 1;
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = r.nextInt(Short.MAX_VALUE);
            }
            Arrays.sort(arr);
            int x = r.nextInt(Short.MAX_VALUE);
            int ans = ans(arr, x);
            int find = findFirst(arr, x);
            if (ans != find) {
                System.out.println("出错了");
                System.out.println(Arrays.toString(arr));
                System.out.println(x);
                System.out.println(ans);
                System.out.println(find);
                break;
            }
        }
    }

    @Test
    public void compareLast() {
        int count = 10000;
        Random r = new Random();
        while (count-- > 0) {
            int n = r.nextInt(Short.MAX_VALUE) + 1;
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = r.nextInt(Short.MAX_VALUE);
            }
            Arrays.sort(arr);
            int x = r.nextInt(Short.MAX_VALUE);
            int ans = lastAns(arr, x);
            int find = findLast(arr, x);
            if (ans != find) {
                System.out.println("出错了");
                System.out.println(Arrays.toString(arr));
                System.out.println(x);
                System.out.println(ans);
                System.out.println(find);
                break;
            }
        }
    }
    //暴力
    public int ans(int[] arr, int n) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == n) {
                return i;
            }
        }
        return -1;
    }

    public int lastAns(int[] arr, int t) {
        for (int i = arr.length - 1; i >= 0; i--) {
            if (arr[i] == t) {
                return i;
            }
        }
        return -1;
    }
}
